package aobing;

/**
 * Test
 *
 * @author Syzer
 * @Description
 * @Date 2021/7/23 10:39
 */
public class FindKth {
    // 快排
    public int findKth(int[] a, int n, int K) {
        // write code here
        return quickSort(a, 0, n - 1, K);
    }

    private int quickSort(int[] arr, int left, int right, int K) {
        if(left > right) {
            return -1;
        }
        int pivot = partition(arr, left, right);
        if(pivot + 1 == K) {
            return arr[pivot];
        } else if(pivot + 1 < K) {
            return quickSort(arr, pivot + 1, right, K);
        } else {
            return quickSort(arr, left, pivot - 1, K);
        }
    }

    private int partition(int[] arr, int left, int right) {
        int midValue = arr[left];
        while(left < right) {
            while(left < right && arr[right] <= midValue) {
                right--;
            }
            swap(arr, left, right);
            while(left < right && arr[left] >= midValue) {
                left++;
            }
            swap(arr, left, right);
        }
        return left;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 堆
    public int findKth1(int[] a, int n, int K) {
        // write code here
        for(int i = 0;i < a.length;i++) {
            if(i < K) {
                siftUp(a, i);
            } else {
                if(a[i] > a[0]) {
                    a[0] = a[i];
                    siftDown(a, 0, K);
                }
            }
        }
        return a[0];
    }

    private void siftDown(int[] arr, int i, int len) {
        int val = arr[i];
        int half = len >>> 1;
        while(i < half) {
            int minIndex = (i << 1) + 1;
            int minValue = arr[minIndex];

            int rightIndex = minIndex + 1;
            if(rightIndex < len && arr[rightIndex] < minValue) {
                minValue = arr[minIndex = rightIndex];
            }

            if(val <= minValue) {
                break;
            }
            arr[i] = minValue;
            i = minIndex;
        }
        arr[i] = val;
    }

    private void siftUp(int[] arr, int i) {
        int val = arr[i];
        while(i > 0) {
            int parentIndex = (i - 1) >>> 1;
            if(val >= arr[parentIndex]) {
                break;
            }
            arr[i] = arr[parentIndex];
            i = parentIndex;
        }
        arr[i] = val;
    }

    public static void main(String[] args) {
        FindKth findKth = new FindKth();
        findKth.findKth(new int[]{1,3,5,2,2},5,3);
    }
}
